#include<stdio.h>
#include<stdlib.h>

struct node 
{ 
int value;
struct node *next
};

void insert(struct node **);
void display(struct node *);
void beginsert(struct node **ptr2,int );
void delete(struct node **);
void len(struct node *);
void count(struct node *);
void max(struct node **);
void min(struct node **);
void append(struct node **);
void extend(struct node **);
void index(struct node **);
void reverse(struct node **);
void pop(struct node **);
void inserti(struct node **);
void MergeSort(struct node **);
void split(struct node *,struct node **,struct node **);
struct node *create();
struct node *SortedMerge(struct node *,struct node *);

void main()
{
struct node *p;
int num1,num;
int x,i,ch;
p=NULL;

do
{

printf("_____________________________________________________\n\n");
printf("PYTHON LIST IMPLEMENTATION THROUGH C\n");
printf("1. Create \n");
printf("2. Append \n");
printf("3. Extend \n");
printf("4. Insert \n");
printf("5. Delete \n");
printf("6. Pop \n");
printf("7. Max \n");
printf("8. Min \n");
printf("9. Index \n");
printf("10. Count \n");
printf("11. Sort \n");
printf("12. Reverse \n");
printf("13. Length \n");
printf("14. Display \n");
printf("15. Exit \n");
printf("______________________________________________________\n\n");

printf("Enter your choice");
scanf("%d",&ch);

switch(ch)
{
case 1:
{
p=create();
break;
}
case 2:
{
append(&p);
break;
}
case 3:
{
extend(&p);
break;
}
case 4:
{
inserti(&p);
break;
}
case 5:
{
delete(&p);
break;
}
case 6:
{
pop(&p);
break;
}
case 7:
{
max(&p);
break;
}
case 8:
{
min(&p);
break;
}
case 9:
{
index(&p);
break;
}
case 10:
{
count(p);
break;
}
case 11:
{
MergeSort(&p);
break;
}
case 12:
{
reverse(&p);
break;
}
case 13:
{
len(p);
break;
}
case 14:
{
display(p);
break;
}
case 15:
{
break;
}
default:
printf("You entered a wrong choice");
}
}
while(ch!=15);
}

struct node *create()
{
int x,i;
struct node *list;
list=NULL;
printf("Enter the number of elements in the link list : ");
scanf("%d",&x);
for(i=0;i<x;i++)
{
insert(&list);
}
return list;
}

// I made this function beginsert..its working..but its not their in python so i commented it out

/*void beginsert(struct node **ptr2,int num2)
{
struct node *te;
te=malloc(sizeof(struct node));
te->value=num2;
if ( *ptr2== NULL)
{
*ptr2=te;
(*ptr2)->next=NULL;
}
else
{
te->next=*ptr2;
*ptr2=te;
}
}
*/

void insert(struct node **ptr)
{
int num;
struct node *t,*s;
printf("Enter the value you want to enter : ");
scanf("%d",&num);
t=malloc(sizeof(struct node));
t->value=num;
t->next=NULL;
if(*ptr==NULL)
{
*ptr=t;
}
else
{
t=*ptr;
while(t->next!=NULL)
{
t=t->next;
}
s=malloc(sizeof(struct node));
s->value=num;
s->next=NULL;
t->next=s;
}
}

void len(struct node *ptr6)
{
int c=0;
while(ptr6!=NULL)
{
c++;
ptr6=ptr6->next;
}
printf("The length is : %d \n",c);
}

void count(struct node *ptr7)
{
int num2;
printf("Enter the number whose count you want to find in the  list : ");
scanf("%d",&num2);
int c1=0;
while(ptr7!=NULL)
{
if(ptr7->value==num2)
{
c1++;
}
ptr7=ptr7->next;
}
printf("The count of %d in the list is : %d \n",num2,c1);
}

void display(struct node *ptr1)
{
while(ptr1!=NULL)
{
printf("%d\n",ptr1->value);
ptr1=ptr1->next;
}
}

void max(struct node **ptr9)
{

int max=-32768;
struct node *temp;

temp=*ptr9;

while(temp->next!=NULL)
{
if(temp->value>max)
{
max=temp->value;
}
temp=temp->next;
}
if(temp->value>max)
{
max=temp->value;
}
printf("The maximum number in the given list is : %d \n",max);
}

void min(struct node **ptr10)
{
int min=32768;
struct node *temp1;

temp1=*ptr10;

while(temp1->next!=NULL)
{
if(temp1->value<min)
{
min=temp1->value;
}
temp1=temp1->next;
}
if(temp1->value<min)
{
min=temp1->value;
}
printf("The minimum number in the given list is : %d\n",min);
}

void append(struct node **ptr7)
{
int num;
struct node *ptr,*p;

printf("Enter the element you want to append : ");
scanf("%d",&num);

ptr=malloc(sizeof(struct node));

ptr->value=num;
ptr->next=NULL;
p=*ptr7;
while(p->next!=NULL)
{
p=p->next;
}
p->next=ptr;
}

void extend(struct node **ptr8)
{
int n,i;
struct node *ptr9,*p;
p=*ptr8;
ptr9=NULL;
printf("How many elements you want to append : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
insert(&ptr9);
}
while(p->next!=NULL)
{
p=p->next;
}
p->next=ptr9;
}

void index(struct node **ptr6)
{
int num,f=0;
int c=0;
struct node *t;
printf("Enter the number whose index you want to find : ");
scanf("%d",&num);
t=*ptr6;
while(t->next!=NULL)
{
if(t->value==num)
{
f=1;
break;
}
c=c+1;
t=t->next;
}
if(f==0)
printf("You entered a wrong choice");
else
printf("The smallest index of %d is %d\n",num,c);
}

void reverse(struct node **ptr)
{
struct node *first;
struct node *rest;

if(*ptr==NULL) return;

first =*ptr;
rest=first->next;


if(rest==NULL)return;

reverse(&rest);

first->next->next=first;
first->next=NULL;
*ptr=rest;
}

void delete(struct node **ptr)
{
struct node *current;
struct node *previous;
struct node *t;
int num,f=0;
previous=*ptr;
current=*ptr;
printf("Enter the number you want to deleted is : ");
scanf("%d",&num);
t=*ptr;
if(num==t->value)
{
previous=NULL;
current=current->next;
//*ptr=(*ptr)->next;
}
else
{
while(t->next!=NULL)
{
if(t->value==num)
{
f=1;
break;
}
previous=current;
current=current->next;
t=t->next;
}
if(f==0)
printf("ERROR\\...You entered a element that is not in the list");
else
previous->next=current->next;
}
}

void pop(struct node **ptr)
{
struct node *current;
struct node *previous;
struct node *t;
int num,x,f=0,c=0;
previous=*ptr;
t=*ptr;
current=*ptr;
printf("Enter the position of the element you want to delete\n");
scanf("%d",&num);
if(num==0)
{
f=1;
previous=NULL;
current=current->next;
x=t->value;
//*ptr=(*ptr)->next;
printf("The deleted item is : %d",x);
}
else
{
while(t->next!=NULL)
{
if(t->value==num)
{
f=1;
break;
}
else
{
previous=current;
current=current->next;
t=t->next;
c=c+1;
}
}
if(f==0)
printf("ERROR\\.... index out of range");
else
{
x=previous->next->value;
previous->next=current->next;
printf("The deleted item is %d\n",x);
}
}
}

void inserti(struct node **ptr)
{
struct node *t,*current,*previous;
int i,num,c=0;
struct node *s;
s=malloc(sizeof(struct node));
current=*ptr;
previous=*ptr;
t=*ptr;
printf("Enter the index at which you want to insert a value");
scanf("%d",&i);
printf("Enter the value you want to insert");
scanf("%d",&num);
if(i==0)
{
s->value=num;
s->next=t;
}
else
{
while(t->next!=NULL)
{
if(c==i)
break;
c=c+1;
t=t->next;
previous=current;
current=current->next;
}
s->value=num;
s->next=current;
previous->next=s;
}
}

void MergeSort(struct node **ptr)
{
struct node *t,*a,*b;
t=*ptr;
if((t==NULL) || (t->next==NULL))
return;
split(t,&a,&b);

MergeSort(&a);
MergeSort(&b);

*ptr=SortedMerge(a,b);
}

void split(struct node *t,struct node **a,struct node **b)
{
struct node *l1,*l2;
if((t==NULL) || (t->next==NULL))
{
*a=t;
*b=NULL;
}
else
{
l1=t;
l2=t->next;
while(l2!=NULL)
{
l2=l2->next;
if(l2!=NULL)
{
l1=l1->next;
l2=l2->next;
}
}
*a=t;
*b=l1->next;
l1->next=NULL;
}
}

struct node * SortedMerge(struct node *a,struct node *b)
{
struct node *result;
result=NULL;
if(a==NULL) return b;
else if(b==NULL) return a;
if(a->value<=b->value)
{
result=a;
result->next=SortedMerge(a->next,b);
}
else
{
result=b;
result->next=SortedMerge(a,b->next);
}
return result;
}

